package leetcode.editor.cn;

//[300]最长递增子序列
public class LongestIncreasingSubsequence300 {
    public static void main(String[] args) {
        Solution solution = new LongestIncreasingSubsequence300().new Solution();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int res = solution.lengthOfLIS(nums);
        System.out.println(res);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //	执行耗时:57 ms,击败了74.16% 的Java用户
        //	内存消耗:42.9 MB,击败了88.18% 的Java用户
        // dp  O(n^2)
        public int lengthOfLIS(int[] nums) {
            if (nums == null || nums.length < 1) return 0;
            int res = 1;
            int len = nums.length;
            int[] dp = new int[len];
//          dp[i] == 选上 i 时的最大 step,  dp[i] = max dp[0....i-1] +1
            for (int i = 0; i < len; i++) {
                dp[i] = 1;//def 每个都是 1.
                int curV = nums[i];
                int maxStemp = 0;
                for (int j = 0; j < i; j++) {
                    if (curV > nums[j]) {
                        maxStemp = dp[j] > maxStemp ? dp[j] : maxStemp;
                    }
                }
                dp[i] = maxStemp + 1;
                res = Math.max(res, dp[i]);
            }
            return res;
        }

        //O nlogn  wait,数学的思路，维护一个 数组， 加速 上面的  for (int j = 0; j < i; j++)   if (curV > nums[j]) {
    }
//leetcode submit region end(Prohibit modification and deletion)

}